rtk 2001

2001.1.1

Tipkanje

1. podnaloga

Predpostavimo, da lahko vse znake, ki jih želimo natipkati, razdelimo v dve skupini: nekatere tipkamo vedno z levo roko, druge pa vedno z desno.

Naloga

Napisana je funkcija dolzina_najdaljsega_podniza(vhod), vendar so vrstice premešane. Uredi jih, da bo iz danega niza funkcija izračunala in vrnila dolžino takega najdaljšega podniza, ki ga je mogoče v celoti natipkati z eno samo roko.

def dolzina_najdaljsega_podniza(vhod):
   """Izračuna dolžino najdaljšega podniza v vhodnem nizu."""
    trenutna_roka = None
    max_z_eno = 0
    ze_tipkamo = False  # Če smo pri prvem znaku, moramo znak obravnavati posebej.
    for crka in vhod:
        nova_roka = s_katero_roko(crka)
    st_s_trenutno = 0
        if not ze_tipkamo:
        trenutna_roka = nova_roka
            st_s_trenutno = 1
        elif nova_roka == trenutna_roka:
            st_s_trenutno += 1
            st_s_trenutno = 1
        elif st_s_trenutno > max_z_eno:
            max_z_eno = st_s_trenutno
            st_s_trenutno = 1
        else:
            ze_tipkamo = True
    return max(max_z_eno, st_s_trenutno)

Na voljo imaš funkcijo s_katero_roko, ki zna za vsak znak povedati, v katero od navedenih dveh skupin spada. Če ga napišemo z levo, nam vrne niz 'leva', sicer pa niz 'desna'.

Vhodni podatki

Niz, sestavljen iz črk, ki jih najdemo na slovenski tipkovnici.

Izhodni podatki

Dolžina najdaljšega podniza danega niza, ki ga je mogoče natipkati z eno samo roko.

Primer

Če se a in e tipkata vedno z levo roko, i, o in u pa vedno z desno, je pri nizu aeiou pravilni odgovor:

>>> dolzina_najdaljsega_podniza('aeiou')
3

Podniz iou lahko namreč natipkamo z desno roko. Poglejmo si še nekaj primerov.

>>> dolzina_najdaljsega_podniza('aaeaiaoaua')
4

Podniz aaea lahko namreč natipkamo z levo roko.

>>> dolzina_najdaljsega_podniza('ouaeauo')
3

Podniz aea lahko namreč natipkamo z levo roko.

  >>> dolzina_najdaljsega_podniza('uaoei')
  1

Nobenih dveh zaporednih znakov ne moremo natipkati z isto roko.

  >>> dolzina_najdaljsega_podniza('iieeoo')
  2

V tem primeru lahko niz ii v celoti natipkamo z desno ali pa ee z levo ali pa oo z desno.

Uradna rešitev

def s_katero_roko(crka):
    """Vrne niz, ki pove, s katero roko natipkamo dano črko."""
    leva = 'qwertasdfgyxcvbQWERTASDFGYXCVB'
    desna = 'zuiopšđhjklčćžnmZUIOPŠĐHJKLČĆŽNM'
    assert crka in leva or crka in desna
    if crka in leva:
        return 'leva'
    else:
        return 'desna'

def dolzina_najdaljsega_podniza(vhod):
    """Izračuna dolžino najdaljšega podniza v vhodnem nizu."""
    trenutna_roka = None
    max_z_eno = 0
    st_s_trenutno = 0
    ze_tipkamo = False  # Če smo pri prvem znaku, moramo znak obravnavati posebej.
    for crka in vhod:
        nova_roka = s_katero_roko(crka)
        if not ze_tipkamo:
            ze_tipkamo = True
            st_s_trenutno = 1
        elif nova_roka == trenutna_roka:
            # Z isto toko kot doslej natipkamo še en znak več.
            st_s_trenutno += 1
        elif st_s_trenutno > max_z_eno:
            # Zamenjamo roko. Mogoče smo z dosedanjo dosegli nov rekord.
            max_z_eno = st_s_trenutno
            st_s_trenutno = 1
        else:
            st_s_trenutno = 1
        trenutna_roka = nova_roka

    # Morda je rekordno zaporedje tisto na koncu niza, zato vrnemo maksimum.
    return max(max_z_eno, st_s_trenutno)

2001.1.4

Pitagorejske trojice

1. podnaloga

Naloga

Napisana je funkcija stevilo_trojic(a, b), ki za dani celi števili $a$ in $b$ ($a$ je manjše ali enako $b$, obe števili pa sta večji ali enaki $1$) ugotovi, koliko je trojic pozitivnih celih števil $(x, y, z)$, za katere je $x^2 + y^2 = z^2$ in je $z$ med $a$ in $b$, lahko je kateremu od njiju tudi enak.

Vrstice so se premešale. Uredi jih, da bo funkcija zopet delovala.

def stevilo_trojic(a, b):
    """Izračuna število pitagorejskih trojic (x, y, z), za katere velja, da je
    z med vključno a in b."""
        while x < z:
    n = 0
    z = a
        x = 1
            y = math.sqrt(z * z - x * x)
    import math
    while z <= b:
            if y.is_integer():
                n += 1
            x += 1
        z += 1
    return n

Vhodni podatki

Dve naravni števili.

Izhodni podatki

Število pitagorejskih trojic, ki ustrezajo pogojem.

Primer

>>> stevilo_trojic(5, 20)
12

Za $a = 5$ in $b = 20$ funkcija vrne število $12$, saj obstaja dvanajst trojic števil, ki ustrezajo zgoraj opisanim pogojem. To so:

$(3, 4, 5)$, $(4, 3, 5)$, $(6, 8, 10)$, $(8, 6, 10)$, $(5, 12, 13)$, $(12, 5, 13)$, $(9, 12, 15)$, $(12, 9, 15)$, $(8, 15, 17)$, $(15, 8, 17)$, $(12, 16, 20)$, $(16, 12, 20)$.

Uradna rešitev

import math
def stevilo_trojic(a, b):
    """Izračuna število pitagorejskih trojic (x, y, z), za katere velja, da je
    z med vključno a in b."""
    n = 0
    z = a
    while z <= b:
        x = 1
        while x < z:
            y = math.sqrt(z * z - x * x)
            if y.is_integer():
                n += 1
            x += 1
        z += 1
    return n